package salvo.jesus.graph.algorithm;

import java.util.Collections;
import java.util.Iterator;
import java.util.Vector;

import salvo.jesus.graph.DirectedAcyclicGraph;
import salvo.jesus.graph.Edge;
import salvo.jesus.graph.Vertex;
import salvo.jesus.graph.Visitor;

/**
 * A concrete subclass of GraphTraversal that performs a topological sort
 * against a directed acyclic graph.
 * 
 * @author  Jesus M. Salvo Jr.
 */

public class TopologicalSorting extends GraphTraversal {

  DirectedAcyclicGraph  dag;

  /**
   * Creates an instance of TopologicalSorting that will perform a
   * topological sort against a directed acyclic graph.
   * 
   * @param dag   The DirectedAcyclicGraph on which topological sorting will be performed.
   */
  public TopologicalSorting( DirectedAcyclicGraph dag ) {
    super( dag );
    this.dag = dag;
  }

  /**
   * Perform a topological sort of the connected set of a directed acyclic graph
   * to which Vertex startat belongs, starting at Vertex startat.
   *
   * @param	startat	  The Vertex to which you want to start the traversal.
   * @param	visited	  Vector of vertices that has been visited,
   *                  in the sequence they were visited.
   * @param visitor   Visitor object to visit each vertex as they are visited.
   *                  Return value of the visitor is ignored.
   */
  public int traverse( Vertex startat, Vector visited, Visitor visitor) {
    int			indexOfstartat;
    Vector		currentadjacentVertices;
    Iterator	iterator;
    Vertex		adjacentVertex;

    // Remove any instance of the vertex being visited.
    visited.remove( startat );
    visited.add( startat );
    // Let the visitor object visit this vertex. Ignore return value.
    visitor.visit( startat );

    // Get the adjacency edge list for the current vertex,
    // from which we can get the adjacent vertices
    currentadjacentVertices = getOutgoingAdjacentVertices( dag, startat );

    // Get an iterator for the adjacency list of the current vertex
    iterator = currentadjacentVertices.iterator( );

    // For each vertex adjacent to the current vertex, visit the vertex,
    // calling this method recursively
    while( iterator.hasNext() ){
      adjacentVertex = (Vertex) iterator.next();
      // Ignore return value of traversal
      this.traverse( adjacentVertex, visited, visitor );
    }
    
    return OK;
  }

  /**
   * Perform a topological sort of the connected set of a directed acyclic graph
   * to which Vertex startat belongs, starting at Vertex startat.
   *
   * @param	startat	  The Vertex to which you want to start the traversal.
   * @param visitor   Visitor object to visit each vertex as they are visited.
   *                  Return value of the visitor is ignored.
   * 
   * @return  A Vector of vertices in the order that they were visited.
   */
  public Vector traverse( Vertex startat, Visitor visitor ) {
    Vector  visited = new Vector();
  
    this.traverse( startat, visited, visitor );
    return visited;
  }

  /**
   * Perform a topological sort of the connected set of a directed acyclic graph
   * to which Vertex startat belongs, starting at Vertex startat.
   *
   * @param	startat	  The Vertex to which you want to start the traversal.
   * 
   * @return  A Vector of vertices in the order that they were visited.
   */
  public Vector traverse( Vertex startat ) {
    return this.traverse( startat, new Visitor());
  }

  /**
   * Perform a reverse topological sort of the connected set of a directed acyclic graph
   * to which Vertex startat belongs, starting at Vertex startat.
   *
   * This method is not part of the GraphTraversal abstract class, but is added
   * here for convenience.
   *
   * @param	startat	  The Vertex to which you want to start the traversal.
   * 
   * @return  A Vector of vertices in the order that they were visited.
   */
  public Vector reverseTraverse( Vertex startat ) {
    Vector sortSequence = this.traverse( startat, new Visitor());
    Collections.reverse( sortSequence );
    return sortSequence;
  }
  
  /**
   * Perform a topological sort of the entire directed acyclic graph.
   * Note that the sequence of vertices in the return Vector will not distinguish
   * between connected components of the graph.
   * 
   * This method is not part of the GraphTraversal abstract class, but is added
   * here for convenience.
   *
   * @return Vector containing the sequence of the vertices visited in the 
   * entire directed acyclic graph, regardless of the connected components of the graph.
   */
  public Vector traverse() {
    Vector	  sortSequence = new Vector();
    Vector	  rootVertices = new Vector();
    Iterator  iterator;

    rootVertices = this.dag.getRoot();
    iterator = rootVertices.iterator();
    while( iterator.hasNext()){
      this.traverse( (Vertex) iterator.next(), sortSequence, new Visitor());
    }

    return sortSequence;
  }
  
  /**
   * Perform a reverse topological sort of the entire directed acyclic graph.
   * Note that the sequence of vertices in the return Vector will not distinguish
   * between connected components of the graph.
   * 
   * This method is not part of the GraphTraversal abstract class, but is added
   * here for convenience.
   *
   * @return Vector containing the sequence of the vertices visited in the 
   * entire directed acyclic graph, regardless of the connected components of the graph.
  */
  public Vector reverseTraverse( ){
    Vector sortSequence = this.traverse();
    Collections.reverse( sortSequence );
    return sortSequence;
  }

  /**
   * returns the vertices adjacent by an outgoing edge
   * to the vertex in the DAG
   * @param dag the DirectedAcyclicGraph
   * @param v   the Vertex
   * @return a Vector of adjacent vertices
   */
  private Vector getOutgoingAdjacentVertices( DirectedAcyclicGraph dag, Vertex v ) {
    Vector    adjacentVertices = new Vector();
    Vector    incidentEdges = dag.getOutgoingEdges( v );
    Iterator  iterator;
    Edge      edge;
    Vertex    oppositeVertex;

    iterator = incidentEdges.iterator();
    while( iterator.hasNext() ) {
      edge = (Edge) iterator.next();
      oppositeVertex = edge.getOppositeVertex( v );
      if( oppositeVertex != null )
        adjacentVertices.add( oppositeVertex );
    }
    
    return adjacentVertices;
  }

    

}

